//给你一个 二进制 字符串 s 和一个整数 k。 
//
// 如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束： 
//
// 
// 字符串中 0 的数量最多为 k。 
// 字符串中 1 的数量最多为 k。 
// 
//
// 返回一个整数，表示 s 的所有满足 k 约束 的子字符串的数量。 
//
// 
//
// 示例 1： 
//
// 
// 输入：s = "10101", k = 1 
// 
//
// 输出：12 
//
// 解释： 
//
// s 的所有子字符串中，除了 "1010"、"10101" 和 "0101" 外，其余子字符串都满足 k 约束。 
//
// 示例 2： 
//
// 
// 输入：s = "1010101", k = 2 
// 
//
// 输出：25 
//
// 解释： 
//
// s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。 
//
// 示例 3： 
//
// 
// 输入：s = "11111", k = 1 
// 
//
// 输出：15 
//
// 解释： 
//
// s 的所有子字符串都满足 k 约束。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 50 
// 1 <= k <= s.length 
// s[i] 是 '0' 或 '1'。 
// 
//
// Related Topics 字符串 滑动窗口 👍 41 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2024-11-13 23:51:20
 * @description 3258.统计满足 K 约束的子字符串数量 I
 */
public class CountSubstringsThatSatisfyKConstraintI{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 CountSubstringsThatSatisfyKConstraintI fun=new CountSubstringsThatSatisfyKConstraintI();
	 	 Solution solution = fun.new Solution();
		  solution.countKConstraintSubstrings("01",1);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*
		 *
		 * 1.枚举，每个区间计算，时间on2 空间on
		 * 2.1用一个数组记录1的个数，其中ar[i]表示从0到此处1的个数
		 * 2.2遍历所有子串，通过长度-ar[i]得到0 的个数，
		 * 2.3比较0和1的个数与k的关系更新答案
		 * */
    public int countKConstraintSubstrings(String s, int k) {
        int n=s.length();
		int [] ar=new int[n];
		int res=0;
		ar[0]=s.charAt(0)-'0';
		for (int i = 1; i < s.length(); i++) {
			ar[i]=ar[i-1]+s.charAt(i)-'0';
		}
		for (int i = 0; i < s.length(); i++) {
			for (int j = i; j <s.length(); j++) {
				int s1=ar[j]-(i==0?0:ar[i-1]);
				int s0=j-i+1-s1;
				if(s0<=k||s1<=k) res++;
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
